데이터베이스 연구회지(SIGDB)
Current Result Document :
| 한글제목(Korean Title) |
도로 네트워크에서 랜드마크 다차원 척도법을 이용한 효율적인 M-트리 대량적재 알고리즘 |
| 영문제목(English Title) |
Efficient M-tree Bulk Loading Algorithm in Road Networks Using Landmark Multidimensional Scaling |
| 저자(Author) |
원소현
권혁윤
Sohyun Won
Hyuk-Yoon Kwon
노웅기
Woong-Kee Loh
|
| 원문수록처(Citation) |
VOL 36 NO. 03 PP. 0091 ~ 0104 (2020. 12) |
한글내용
(Korean Abstract) |
본 연구에서는 도로 네트워크를 위한 M-트리 대량적재(bulk loading) 알고리즘을 제안한다. 도로 네트워 크는 매우 동적이며, 차량의 이동, 예측하지 못한 공사와 사고 등으로 인하여 교통 상황이 끊임없이 변화한다. 도로 네트워크 응용에서는 이러한 변화를 반영하도록 인덱스를 주기적으로 재구성하는 것이 필수적이다. 각 각의 변화에 대하여 기존의 인덱스를 수정하기보다는 전체 도로 네트워크 데이터셋에 대한 새로운 인덱스를 빠르게 재구성하는 대량적재가 효율적이다. 기존의 M-트리 대량적재 알고리즘은 ‘비싼’ 최단경로 거리 계산 과 디스크 페이지 엑세스를 과도하게 수행하여 충분한 성능을 거두지 못하였다. 본 연구에서 제안하는 M-트 리 대량적재 알고리즘은 랜드마크 다차원 척도법(Landmark Multidimensional Scaling, LMDS)을 이용하 여 최단경로 거리 계산을 대폭 줄인다. 또한, 각 노드를 한번씩만 디스크에 저장하고 더 이상 읽지 않음으로 써 디스크 액세스 횟수를 크게 줄였다. 실험 결과, 제안된 알고리즘은 기존의 알고리즘에 비하여 단일 쓰레드 버전은 최대 21.3배, 다중 쓰레드 버전(동시 쓰레드 64개)은 최대 106배까지 M-트리 생성 성능이 향상되었고, 제안된 알고리즘으로 생성한 M-트리를 이용한 k-최근접 객체(k-nearest neighbor) 검색의 성능이 최대 1.22 배까지 향상되었다. |
영문내용
(English Abstract) |
In this study, we propose an algorithm for M-tree bulk loading in road networks. Road networks are highly dynamic; traffic situation changes constantly owing to vehicle movements and unpredicted constructions and accidents. Thus, it is crucial for road network applications to periodically reorganize the index to fully reflect the changes. In such a circumstance, rather than modifying the existing index for each of the changes, it is more efficient to quickly bulk load a new index for the entire road network. The previous M-tree bulk loading algorithms heavily conduct ‘expensive’ shortest-path distance computations and disk page accesses, thereby degrading their performances. The algorithm proposed in this study reduces the number of shortest-path distance computations using landmark multidimensional scaling (LMDS). In addition, since our algorithm stores M-tree nodes in disk and does not access them again, the number of disk page accesses is also dramatically reduced. Experimental results demonstrated that our algorithm outperformed the previous algorithm by up to 21.3 times (single-thread version) and 106 times (multi-thread version with 64 concurrent threads) for M-tree construction and that the performance of the k-nearest neighbor (k-NN) search using the M-tree built by our algorithm was also improved by up to 1.22 times. |
| 키워드(Keyword) |
텍스트 유사도 측정
비정형 데이터 분석
SNS 사용자 위치 예측
Text similarity measurement
Unstructured data analysis
SNS user location prediction
M-트리
대량적재
도로 네트워크
랜드마크 다차원 척도법
M-tree
bulk loading
road network
landmark multidimensional scaling
|
| 파일첨부 |
PDF 다운로드
|
